// 路径问题

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame)
    {
        int m = frame.size(); int n = frame[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];

        return dp[m][n];
        
    }
};

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        // 到达最后一行的最小值
        // dp[i]j] = min(dp[i - 2[j - 1], dp[i - 1][j - 1], dp[i - 1][j - 2]) + matrix[i - 1][j - ];
        // 
        
        // 初始化，填表时存在，左边界 与 右边界 的填表访问非法元素问题，将所有dp表初始化为 INT_MAX
        // 第一行 dp 初始化 为0
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 2, INT_MAX));
        
        for(int i = 0, j = 0; j < n + 2; j++) dp[i][j] = 0;

        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1])) + matrix[i - 1][j - 1];

        // 找到最后一行的最小dp值
        int ret = INT_MAX;
        for(int j = 1; j <= n; j++)
            ret = min(ret, dp[m][j]);

        return ret;
    }
};
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid)
    {
        // 到达结尾时dp的最小值
        // dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];

        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m + 1,  vector<int>(n + 1, INT_MAX));
        
        // 初始化问题，将 dp表初始化为 INT_MAX 来规避边界的影响，同时为了保证填表正确，需要将 dp[0][1] dp[1][0] = 0
        dp[0][1] = dp[1][0] = 0;
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
        return dp[m][n];
    }
};